package org.example.algorithm.dp;

import java.util.ArrayList;
import java.util.List;

public class LengthOfLongestSubsequenceSolution {

    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        nums.add(4);
        nums.add(1);
        nums.add(3);
        nums.add(2);
        nums.add(1);
        nums.add(5);
        LengthOfLongestSubsequenceSolution solution = new LengthOfLongestSubsequenceSolution();
        int target = 7;
        int res = solution.lengthOfLongestSubsequence(nums, target);
        System.out.println(res);
    }

    //简化内存占用
    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        int[] dp = new int[target+1];
        for (int j=0;j<=target;j++) {
            if (nums.get(0) == j) {
                dp[j] = 1;
            } else {
                dp[j] = -1;
            }
        }
        for (int i=1;i<nums.size();i++) {
            for (int j=target;j>=0;j--) {
                if(nums.get(i) < j) {
                    int temp = dp[j-nums.get(i)];
                    dp[j] = Math.max(dp[j], temp == -1 ? -1 : temp + 1);
                } else if (nums.get(i) == j) {
                    int temp = dp[0];
                    dp[j] = Math.max(dp[j], temp == -1 ? 1 : temp + 1);
                }
            }
        }
        return dp[target];
    }

    //4,1,3,2,1,5 target=7
    //dp[i][j]代表【0，i】和为j的最大值
    //nums[i] <= j:dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums.get(i)] + 1)
    //nums[i] > j:dp[i][j] = dp[i-1][j]
    public int lengthOfLongestSubsequence2(List<Integer> nums, int target) {
        int[][] dp = new int[nums.size()][target+1];
        for (int j=0;j<=target;j++) {
            if (nums.get(0) == j) {
                dp[0][j] = 1;
            } else {
                dp[0][j] = -1;
            }
        }
        for (int i=1;i<nums.size();i++) {
            for (int j=0;j<=target;j++) {
                if (nums.get(i) > j) {
                    dp[i][j] = dp[i-1][j];
                } else if(nums.get(i) < j) {
                    int temp = dp[i-1][j-nums.get(i)];
                    dp[i][j] = Math.max(dp[i-1][j], temp == -1 ? -1 : temp + 1);
                } else {
                    int temp = dp[i-1][0];
                    dp[i][j] = Math.max(dp[i-1][j], temp == -1 ? 1 : temp + 1);
                }
            }
        }
        return dp[nums.size()-1][target];
    }
}
